package 单周赛.history;

import java.util.*;

/**
 *
 */
public class 第356场单周赛 {

    public static void main(String[] args) {

        第356场单周赛 impl = new 第356场单周赛();

        System.out.println(impl.countCompleteSubarrays(new int[]{5, 5, 5, 5}));

        System.out.println(impl.minimumString("ab", "ba", "aba"));

    }

    public int numberOfEmployeesWhoMetTarget(int[] hours, int target) {
        int cnt = 0;
        for (int hour : hours) {
            if (hour >= target) {
                cnt++;
            }
        }
        return cnt;
    }

    /**
     * 动态规划
     * 以 i 结尾的子数组是 [0,i-1] 的所有子数组 + nums[i]
     * 用哈希表记录 [0,i-1] 的所有子数组，遍历过程中统计满足
     * 条件的子数组数量
     */
    public int countCompleteSubarrays(int[] nums) {
        long allCnt = Arrays.stream(nums).distinct().count();
        int cnt = 0;
        List<Set<Integer>> preList = new ArrayList<>();

        for (int num : nums) {
            for (Set<Integer> set : preList) {
                set.add(num);
                if (set.size() == allCnt) {
                    cnt++;
                }
            }
            if (allCnt == 1) {
                cnt++;
            }
            Set<Integer> set = new HashSet<>();
            set.add(num);
            preList.add(set);
        }

        return cnt;
    }

    /**
     * 滑动窗口
     * 窗口 [left,right] 中不同的数量正好满足条件，那么
     * 以 right 结尾满足的条件子数组数量为 left-0+1，
     * left 左边开头的子数组包含 [left,right] 一定满足条件
     */
    public int countCompleteSubarrays2(int[] nums) {
        int cnt = 0;
        int left = 0;

        long totalDiff = Arrays.stream(nums).distinct().count();
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
            while (map.size() == totalDiff) {
                map.put(nums[left], map.get(nums[left]) - 1);
                if (map.get(nums[left]) == 0) {
                    map.remove(nums[left]);
                }
                left++;
            }
            // while循环结束后 left 刚好不满足条件，统计的是 [0,left-1] 的长度
            cnt += left;
        }
        return cnt;
    }

    /**
     * 贪心+枚举
     * a 和 b 相连， a 的最长后缀匹配 b 的最长前缀，需要考虑 a 包含
     * b 或者 b 包含 a 的情况
     */
    public String minimumString(String a, String b, String c) {
        PriorityQueue<String> priorityQueue =
                new PriorityQueue<>((a1, a2) ->
                        a1.length() == a2.length() ?
                                a1.compareTo(a2) :
                                a1.length() - a2.length());

        priorityQueue.add(link(link(a, b), c));
        priorityQueue.add(link(link(a, c), b));
        priorityQueue.add(link(link(b, a), c));
        priorityQueue.add(link(link(b, c), a));
        priorityQueue.add(link(link(c, a), b));
        priorityQueue.add(link(link(c, b), a));

        priorityQueue.add(link(a, link(b, c)));
        priorityQueue.add(link(a, link(c, b)));
        priorityQueue.add(link(b, link(a, c)));
        priorityQueue.add(link(b, link(c, a)));
        priorityQueue.add(link(c, link(a, b)));
        priorityQueue.add(link(c, link(b, a)));

        return priorityQueue.poll();
    }

    private String link(String a, String b) {
        if (a.contains(b)) {
            return a;
        }
        if (b.contains(a)) {
            return b;
        }

        int aIdx = 0;

        while (aIdx < a.length()) {
            if (a.length() - aIdx > b.length()) {
                aIdx++;
                continue;
            }

            boolean flag = true;
            for (int i = aIdx, j = 0; i < a.length(); i++, j++) {
                if (a.charAt(i) != b.charAt(j)) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                break;
            }
            aIdx++;
        }

        return new StringBuilder()
                .append(a)
                .append(b.substring(a.length() - aIdx)).toString();
    }

}
